Recursive dynamic programming (DP) techniques are used in many different and varied applications such as speech recognition and genetic sequence comparison. In both of these cases, and in many others, the unifying principle is optimization. In all cases, the execution of the optimizing equations is computationally intensive and in some cases so intensive that the DP method of solution is not practical except for research as, for example, in a speech recognition system wherein the computational burden prohibits real-time operation.
The DP recursive expressions have an inherent parallelism that is suitable for implementation on parallel computer structures. General purpose systolic processors, such as Intel's "iWarp", have been applied to the task. Also, fine grain parallel computing neural networks have been used to implement DP techniques for speech recognition (for example, "Speaker-Independent Word Recognition Using Dynamic Programming Neural Networks," Sakoe, H., Isotani, R., Yoshida, K., Iso, K., and Watanabe, T., International Conference on Acoustics, Speech and Signal Processing, 1989, Vol. 1, pp. 29-32).
A handwriting recognition algorithm described by C. C. Tappert in "Cursive Script Recognition by Elastic Matching", IBM J. Res. Develop. Vol. 26, No. 6, Nov. 1982, pp. 79-85, is based on DP methods and uses a recursive distance metric for comparing a vector element in an unknown script vector with various elements of a prototype script vector. The classification method uses elastic coding at the letter level, allows any letter to follow any letter, and finds the optimal letter sequence which uses all the data points of the input word. The decoder finds the sequence of prototype letters that best matches the input word. The optimal DP recursive relationship is of the form ##EQU1## where D.sub.k (i, j) is the cumulative minimum distance between point i in the unknown and point j in prototype k. The first term on the right hand side of equation (1), d.sub.k (i, j), is a local difference or distance metric that compares point i of the unknown with point j of the prototype k. The second additive term is the minimum of several possible cumulative distances computed on the previous columns of the lattice as determined by the range of the integer column (or elasticity) parameter, 1. For the general, non-boundary case, Tappert assigned a range of 1=0, 1, 2 which only involved the present (1=0) and the past two (1=1, 2) prototype data points. The range of 1 provides for continuity and elasticity (time-warp) in the comparison of the unknown and the prototype k.
Equation (1) is of sufficient generality that it is useful in classification procedures for a large variety of applications. The current invention relates to a classification system that uses a network lattice structure that allows for the efficient calculation of DP recursions using the form of equation (1).